import java.util.HashMap;
import java.util.ArrayList;
import java.io.*;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
import java.util.Iterator;
import java.util.HashSet;
import java.util.Stack;
import java.util.StringTokenizer;

public class Lexer {

	private ArrayList<String> parsedLines = new ArrayList<String>();
	private HashMap<String, String> parsedRegex= new HashMap<String, String>();
	private HashMap<String, String> charClassNames= new HashMap<String, String>();
	private boolean legal;
 	private static final Map<Character, Integer> OPERATORS = new HashMap<Character, Integer>();
    static {
        OPERATORS.put('*', 10); //int is the precedence
        OPERATORS.put('+', 10);
        OPERATORS.put('|', 0);
        OPERATORS.put(Character.toChars(129)[0],  5); //CONCATENATE
    }
	private ArrayList<String> tokenNames = new ArrayList<String>();
	public DFA dfa; 
	private HashMap<String, NFA> tokenNFAs = new HashMap<String, NFA>();
	
	public static Lexer getLexer(String filename){
		//In theory, the only thing we need to know at the end is the dfa
		DFA dfa = DFA.load(filename + ".dfa");
		if (dfa == null){//We haven't saved it before
			return new Lexer(filename);
		}
		else{
			Lexer lex = new Lexer();
			lex.dfa = dfa;
			return lex;
		}
	}
	
	public Lexer(){
		
	}
	
	public Lexer(String filename){
		//Lexer mylexer= new Lexer();
		
		ReadFromSpecFile(filename);
		//mylexer.ReadFromSpecFile("test.txt");
		
		buildSets();
		//mylexer.buildSets();
		
		//HashMap<String, String> mysethash = getParsedRegex();
		/*for(String key: mysethash.keySet()){
			System.out.print(key+"\n");
			System.out.print(mysethash.get(key)+"\n");
			System.out.print(RPNparser.infixToRPN(mysethash.get(key))+"\n");
		}*/
		buildNFATable();
		buildWholeNFA();
		dfa.renameNodes();
		dfa.minimize(tokenNames);
	}

	public void ReadFromSpecFile(String filename){
		try{
			FileInputStream fstream = new FileInputStream(filename);
			DataInputStream in = new DataInputStream(fstream);
			BufferedReader br = new BufferedReader(new InputStreamReader(in));
			String strLine;
			int section = 0;
			StringTokenizer stk;
			while ((strLine = br.readLine()) != null)   {
				if (strLine.length()>1){
					if(!(strLine.charAt(0)=='%' && strLine.charAt(1)=='%')){ //parse out comments
						strLine=removewhitespace(strLine);
						parsedLines.add(strLine);
						if (section >= 2){
							stk = new StringTokenizer(strLine, " ");
							tokenNames.add(stk.nextToken());//We found the start of the token defs
						} else {
							stk = new StringTokenizer(strLine, " ");
							charClassNames.put(stk.nextToken(), "");
						}
					}
					else{
						section++;
					}
				}
			}
			in.close();
		}catch (Exception e){
			System.err.println("Error: " + e.getMessage());
		}
		return;
	}
	
	public void buildWholeNFA(){
		//Set<String> tokenNames = tokenNFAs.keySet();
		System.out.println("Starting buildWholeNFA");
		NFA bigNFA = new NFA();
		Node startNode = new Node();
		int i = 1;
		for (String curname : tokenNames){
			//System.out.println("Dealing with " + i++);
			startNode.addTransitions(NFA.EPS, tokenNFAs.get(curname).start);
		}
		bigNFA.start = startNode;
		dfa = new DFA(bigNFA);
		System.out.println("Finishing buildWholeNFA");
	}

	public ArrayList<String> getParsedLines(){
		return parsedLines;
	}
	public HashMap<String, String> getParsedRegex(){
		return parsedRegex;
	}

	// the main parse function, it will process the file line by line and associate a regex with each line
	private void buildSets(){
		String current;	
		String name;
		String regex;
		int index;


		for(int i=0;i<parsedLines.size();i++){
			current=parsedLines.get(i);
			current=removewhitespace(current);
			index=current.indexOf(" ");
			if(index<=0){
				legal=false;
				return;
			} //illegal

			//picks out the name, and the regex
			name=current.substring(0, index);
			regex=current.substring(index); 
			regex=ProcessEscapeChar(regex); //replaces escape chars with unprintable chars
			if (!parsedRegex.isEmpty()){ //replaces pre-defined sets with their regex

				for (String key:parsedRegex.keySet()){
					regex=regex.replace(key, parsedRegex.get(key));
				}
			}
	//		System.out.print("hi"+regex+"\n");
			//replaces exclusion sets with regex
			while (regex.indexOf("[^")!= -1){
				regex=ProcessExclusion(regex);
			}
		//	System.out.print(regex+"\n");
			//process range operators
			while (regex.indexOf("[") != -1){
			//	System.out.print(regex+"\n");
				regex=ProcessRange(regex);
			}
			//expand dots
			regex=ProcessDot(regex);			
			regex=regex.replace(".",SetToString(DefToSet(" -~")));
			//add concatenate and empty strings
			regex='('+ProcessImpliedOper(regex)+')';
			//store the regex
			parsedRegex.put(name, regex);
			System.out.print(regex+"\n");
		}
		return;
	}
	//This will replace all escape characters with non printable characters and it also removes all spaces
	
	
	public String ProcessDot(String input)
	{
			String replacement;
			replacement=SetToString(DefToSet(" -~"));
			replacement=replacement.replace("\\", Character.toString(Character.toChars(136)[0]));
			replacement=replacement.replace(" ", Character.toString(Character.toChars(137)[0]));
			replacement=replacement.replace("*", Character.toString(Character.toChars(130)[0]));
			replacement=replacement.replace("+", Character.toString(Character.toChars(131)[0]));
			replacement=replacement.replace(".", Character.toString(Character.toChars(132)[0]));
			replacement=replacement.replace("|||","|"+Character.toString(Character.toChars(133)[0])+"|");
			replacement=replacement.replace("|(|", "|"+Character.toString(Character.toChars(134)[0])+"|");
			replacement=replacement.replace("|)|", "|"+Character.toString(Character.toChars(135)[0])+"|");
			replacement=replacement.replace("?", Character.toString(Character.toChars(138)[0]));
			replacement=replacement.replace("[", Character.toString(Character.toChars(139)[0]));
			replacement=replacement.replace("]", Character.toString(Character.toChars(140)[0]));
			replacement=replacement.replace("'", Character.toString(Character.toChars(141)[0]));
			replacement=replacement.replace("\"", Character.toString(Character.toChars(142)[0]));		
			replacement=replacement.replace("^", Character.toString(Character.toChars(143)[0])); //char class only
			replacement=replacement.replace("-", Character.toString(Character.toChars(144)[0])); //char class only*/
			replacement=replacement.replace("$", Character.toString(Character.toChars(145)[0]));			
			replacement=input.replace(".",replacement);
			return replacement;
	}
	
	public String ProcessEscapeChar(String input){

		input=input.replace("\\\\", Character.toString(Character.toChars(136)[0]));
		input=input.replace("\\ ", Character.toString(Character.toChars(137)[0]));
		input=input.replace("\\*", Character.toString(Character.toChars(130)[0]));
		input=input.replace("\\+", Character.toString(Character.toChars(131)[0]));
		input=input.replace("\\.", Character.toString(Character.toChars(132)[0]));
		input=input.replace("\\|", Character.toString(Character.toChars(133)[0]));
		input=input.replace("\\(", Character.toString(Character.toChars(134)[0]));
		input=input.replace("\\)", Character.toString(Character.toChars(135)[0]));
		input=input.replace("\\?", Character.toString(Character.toChars(138)[0]));
		input=input.replace("\\[", Character.toString(Character.toChars(139)[0]));
		input=input.replace("\\]", Character.toString(Character.toChars(140)[0]));
		input=input.replace("\\'", Character.toString(Character.toChars(141)[0]));
		input=input.replace("\\\"", Character.toString(Character.toChars(142)[0]));		
		input=input.replace("\\^", Character.toString(Character.toChars(143)[0])); //char class only
		input=input.replace("\\-", Character.toString(Character.toChars(144)[0])); //char class only*/
		input=input.replace("\\$", Character.toString(Character.toChars(145)[0]));
		//removes spaces
		input=input.replace(" ", "");
		return input;
	}
	//this replaces parsed exclusion sets with the appropriate regex using Set
	public String ProcessExclusion(String input){
		int index1;
		int index2;
		String ret;
		Set<String> tempset1=new HashSet<String>();
		Set<String> tempset2=new HashSet<String>();
		//System.out.print(input+"\n");
		index1=input.indexOf("[^");
		index2=input.indexOf(']', index1);
		tempset1=DefToSet(input.substring(index1+2,index2));//exclude this set
		if (input.charAt(index2+3)=='['){
			index1=index2+4;
			index2=input.indexOf(']', index1);
			tempset2=DefToSet(input.substring(index1, index2));
		} else {
			index1=index2+3;
			index2=input.indexOf(')',index1);
			tempset2=StringToSet(input.substring(index1+1,index2));
		}
		ret=input.substring(0,input.indexOf("[^"))+SetToString(SetSubtract(tempset2, tempset1));
		if(input.charAt(index2)==']'){ret+=input.substring(index2+1);} else {ret+=input.substring(index2+2);}
		return ret;
	}
	
	public String removewhitespace(String input)
	{
		for (int i=0; i<32;i++){
			input=input.replace(Character.toString(Character.toChars(i)[0]),"");
		}
		return input;
		
	}
	
//this replaces the range operator with the equivalent regex
	public String ProcessRange(String input){
		int index1;
		int index2;
		index1=input.indexOf("[");
		index2=input.indexOf(']', index1);
		input=input.substring(0,index1)+SetToString(DefToSet(input.substring(index1+1,index2)))+
		input.substring(index2+1);
		return input;
	}
	//subtract set 2 from set 1
	public Set<String> SetSubtract(Set<String> set1, Set<String> set2){
		Set<String> myset=new HashSet<String>(set1);
		if(!set2.isEmpty()){
			Iterator<String> myiterator=set2.iterator();
			myset.remove(myiterator.next());
			while (myiterator.hasNext()){
				myset.remove(myiterator.next());
			}
		}		
		return myset;
	}

	public Set<String> DefToSet(String def){
		Set<String> myset=new HashSet<String>();
		for (int i=0;i<def.length();i++){
			if(def.charAt(i)!='-'){myset.add(Character.toString(CharConvert(def.charAt(i))));} //this is the only operator we expect
			else {
				if (i==0 || (i+1)>=def.length()) {legal=false;return null;} //range error
				for (int j=def.charAt(i-1);j<def.charAt(i+1);j++){
					myset.add(Character.toString(CharConvert((char)j)));
				}
			}
		}
		return myset;
	}

	public char CharConvert(char input){
		if(input=='*'){ return Character.toChars(130)[0];}
		if(input=='+'){ return Character.toChars(131)[0];}
		//if(input=='.'){ return Character.toChars(132)[0];}
		if(input=='|'){ return Character.toChars(133)[0];}
		if(input=='('){ return Character.toChars(134)[0];}
		if(input==')'){ return Character.toChars(135)[0];}
		if (input=='$'){return Character.toChars(145)[0];}
		return input;
	}

	public char ReverseCharConvert(char input){
		if(input == 136){return '\\';}
		if(input == 137){return ' ';}
		if(input == 130){return '*';}
		if(input == 131){return '+';}
		if(input == 132){return '.';}
		if(input == 133){return '|';}
		if(input == 134){return '(';}
		if(input == 135){return ')';}
		if(input == 138){return '?';}
		if(input == 139){return '[';}
		if(input == 140){return ']';}
		if(input == 141){return '\'';}
		if(input == 142){return '"';}
		if(input == 143){return '^';}
		if(input == 144){return '-';}
		if(input==145){return '$';}
		return input;
	}
	//converts a set to a regex
	public String SetToString(Set<String> input){
		String output="(";
		if(!input.isEmpty()){
			Iterator<String> myiterator=input.iterator();
			output+=myiterator.next();
			while (myiterator.hasNext()){
				output+="|"+myiterator.next();
			}
		}
		output+=')';
		return output;
	}
	//converts a specific type of regex to a set
	public Set<String> StringToSet(String input){
		Set<String> myset=new HashSet<String>();
		int index=input.lastIndexOf('(');
		if (input.length()<3){return myset;}
		for (int i=index+1;i<(input.length()-index);i=i+2)
		{
			myset.add(Character.toString(input.charAt(i)));
		}
		return myset;
	}
	//adding empty strings and concatenate operators
	public String ProcessImpliedOper(String regex){
		if (regex.length()>1){
			for (int i=1;i<regex.length();i++){
				if (regex.charAt(i)=='|' && regex.charAt(i-1)=='('){
					regex=regex.substring(0,i)+Character.toString(Character.toChars(145)[0])+regex.substring(i);
				}
				if (regex.charAt(i)==')' && regex.charAt(i-1)=='|'){
					regex=regex.substring(0,i)+Character.toString(Character.toChars(145)[0])+regex.substring(i);
				}
				if (regex.charAt(i)=='|' && regex.charAt(i-1)=='|'){
					regex=regex.substring(0,i)+Character.toString(Character.toChars(145)[0])+regex.substring(i);
				}
				if (!isOperator(regex.charAt(i)) && !isOperator(regex.charAt(i-1)) && regex.charAt(i-1)!='(' && regex.charAt(i)!=')'){
					regex=regex.substring(0,i)+Character.toString(Character.toChars(129)[0])+regex.substring(i);					
				}
				if((regex.charAt(i-1)=='*' || regex.charAt(i-1)=='+') && !isOperator(regex.charAt(i)) && (regex.charAt(i)!=')')){
					regex=regex.substring(0,i)+Character.toString(Character.toChars(129)[0])+regex.substring(i);
				}
			}
		}
		return regex;
	}
// this will build the NFA using the reverse polish form of a regex
	public NFA buildNFA(String tokenName){
		if (!parsedRegex.containsKey(tokenName)){return null;}
		Stack<NFA> stack = new Stack<NFA>();
		String RPN=infixToRPN(parsedRegex.get(tokenName));
		NFA temp1;//=new NFA();
		NFA temp2;//=new NFA();
		char current;
		for (int i=0; i< RPN.length(); i++){
			current = RPN.charAt(i);
			if (current== '*'){
				temp1=stack.pop();
				//stack.push(temp1.star());
				stack.push(NFA.star(temp1, tokenName));
				continue;
			}
			if (current== '|'){
				temp1=stack.pop();
				temp2=stack.pop();
				//stack.push(temp2.union(temp1));
				stack.push(NFA.union(temp2, temp1, tokenName));
				continue;
			}
			if (current== 129){
				temp1=stack.pop();
				temp2=stack.pop();
				//stack.push(temp2.concatenate(temp1));
				stack.push(NFA.concatenate(temp2, temp1, tokenName));
				continue;
			}
			if (current== '+'){
				temp1=stack.pop();
				//temp2=temp1.star();
				temp2 = NFA.star(temp1, tokenName);
				//stack.push(temp1.concatenate(temp2));
				stack.push(NFA.concatenate(temp1, temp2, tokenName));
				continue;
			}
			stack.push(new NFA(ReverseCharConvert(current), tokenName));
		}
		return stack.pop();
	}


	//This will try to scan a regex file and build the scanners, and returns true if the syntax was legal
	//and false otherwise. 
	public boolean buildScanner(String filename){
		legal=true;
		parsedRegex.clear();
		ReadFromSpecFile(filename);
		buildSets();
		return legal;
	}
	
	public void buildNFATable(){
		Set<String> tokenNames = parsedRegex.keySet();
		//NFA curNFA;
		for (String curname : tokenNames){
			tokenNFAs.put(curname, buildNFA(curname));
		}
	}
	

    
    private static boolean isOperator(Character token) {
        return OPERATORS.containsKey(token);
    }
    
    private static int cmpPrecedence(Character token1, Character token2) {
        return OPERATORS.get(token1) - OPERATORS.get(token2);
    }
    
    //Converts infix notation of the regex to reverse polish notation via shunting yard algorithm
    public static String infixToRPN(String input) {
        String output="";
        Stack<Character> stack = new Stack<Character>();
        for (int i=0; i<input.length(); i++) {
            if (isOperator(input.charAt(i))) {
                while (!stack.empty() && isOperator(stack.peek())) {
                    if (cmpPrecedence(input.charAt(i), stack.peek()) <= 0)
                    {
                        output+=stack.pop(); 
                        continue;
                    }
                    break;
                }
                stack.push(input.charAt(i));
            } else if (input.charAt(i)=='(') {
                stack.push(input.charAt(i));  
            } else if (input.charAt(i)==')') {
                while (!stack.empty() && !(stack.peek()=='(')) {
                    output+=stack.pop(); 
                }
                stack.pop(); 
            } else {
                output+=input.charAt(i);
            }
        }
        while (!stack.empty()) {
            output+=stack.pop(); 
        }
        return output;
    }
    
    public ArrayList<ArrayList<String>> scanFile(String filename){
    	ArrayList<ArrayList<String>> tokens = new ArrayList<ArrayList<String>>();
    	String curline;
    	try{
    		FileWriter tokenfw = new FileWriter(new File(filename + ".tokens"));
    		Scanner scan = new Scanner(new File(filename));
    		while(scan.hasNext()){
    			curline = scan.nextLine();
    			tokens.add(dfa.runDFA(curline));
    			
    		}
    		for (int i = 0; i < tokens.size(); i++){
    			tokenfw.write(tokens.get(i).toString());
    			if (i != tokens.size()-1){
    				tokenfw.write("\n");
    			}
    		}
    		tokenfw.close();
    	}
    	catch(Exception e){
    		e.printStackTrace();
    	}
    	return tokens;
    }

	public static void main(String[] args) {

		Lexer mylexer= new Lexer("test.txt");

		System.out.println(mylexer.scanFile("testinput.txt"));
		

	}

}
